\pagenumbering{arabic}



\newpage

\section{导言}

\subsection{旅行商问题}

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。

最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1\%内。

从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络。

\subsection{遗传算法}

\subsubsection{遗传算法简介}

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

\subsubsection{遗传算法的执行过程}

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.75]{GA.png}
	\caption{遗传算法执行过程图解}
\end{figure}

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。

初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

\section{实验过程}

\subsection{遗传算法在旅行商问题中的思想流程}

程序总体围绕了遗传算法的三个主要步骤：选择--复制，交叉，变异。

\subsubsection{变量介绍}

。给定了\textbf{num\_total}条染色体(本次实验中取为50)。每条染色体都是除首位外不重复的点组成，首尾相同保证路线是闭合的，所以一条染色体包含\textbf{总城市数量+1}个点。这个种群被记录在一个\textbf{fruit}数组变量中，每两个城市之间的距离构成了一个距离矩阵，记录\textbf{dis\_mat}变量中。

种群适应度用\textbf{score}进行记录，利用\textbf{Best\_list} 记录最优城市序列。

\subsubsection{保留更优的个体——选择与复制}

在旅行商问题中，适应度定义为\textbf{路线总长度的倒数}。我们采用\textbf{轮盘赌}的方式对父代进行选择，首先将所有父代的适应度相加，然后用每一个父代的适应度除以总和作为这个父代被选择的概率，然后按照计算出的概率随机选择父代。这样做的原因是为了保留更优质的父代，且为了淘汰劣质父代，我们依然限定选择的总父代数上限是\textbf{num\_total}。

\subsubsection{生成新的个体——交叉}

对于每两个父代，随机生成两个位置，作为染色体交叉片段的起始位置与终止位置。这里要注意的是需要解决交叉后交叉片段与原编码冲突的问题。

\begin{figure}[h]
	\subfigure[交叉结果出现冲突]{
		\includegraphics[width=0.5\linewidth]{c1.png}
	}
	\subfigure[建立映射关系]{
		\includegraphics[width=0.5\linewidth]{c2.png}
	}
	\subfigure[最终结果]{
		\includegraphics[width=0.5\linewidth]{c3.png}
	}
	\caption{解决交叉冲突的例子}
	\label{example}
\end{figure}

考虑图\ref{example}所示的基因片段，在交叉过后，新交叉过来的片段的编码与原染色体产生冲突，这时只需要根据交叉的片段建立映射表，对于第一条染色体\textbf{交叉片段以外的点}根据映射表\textbf{从左往右映射}，对于第二条染色体\textbf{交叉片段以外的点}根据映射表\textbf{从右往左映射}。如此以来便可以解决冲突问题。

\subsubsection{防止陷入局部最优——变异}

虽然仅通过交叉就可以产生后代，但如果只有交叉，那么迭代过程中产生的新解永远只可能是初始种群中已有模式块的组合。如果初始种群中缺失了构建最优解的关键模式，仅通过交叉是无法得到最优解的。

本次实验中采用的变异模式是\textbf{旋转变异}，即随机选择一个染色体片段进行颠倒。选择该变异模式的原因有：

\begin{enumerate}
	\item 不破坏已经规划好的路线的相对性。一个染色体片段的城市一定是经过大量选择后选出的较优的排列顺序，因此变异不应大幅度改变这种排列顺序。
	\item 使得关键基因位置有出现最优解关键模式的可能。
	\item 仅仅随机交换两个城市的顺序也可以达到相同的结果，但产生的后代的多样性也会因此降低，所以采用旋转而不采用随机交换也是基于此考虑。如果后代的适应度差，在下一次选择的时候有极大的概率不会选择到这一后代。
\end{enumerate}


\subsection{遗传算法执行流程}

用户可以在程序中事先规定种群大小与遗传次数。经过多次实验我们发现，对于不超过200个城市的数据，采用50的种群大小和1500的迭代次数便能收敛到较好的最优解。程序会随机排列所有的城市，作为一个可行解。这个过程重复50次(一开始设定的种群大小)，作为初始种群的染色体构成，下面开始整个遗传算法的执行过程。

首先是父代的选择，对于每一个种群，利用轮盘赌的方式选出两个染色体作为父代，这两个父代进行交叉得到两个子代。这两个子代有一定概率会变异(可以预先设定，本次实验设定为0.2)，分别计算这两个子代的适应度，将适应度较大的那个子代加入到下一代中。如果子代中的城市排列顺序比当前记录的最优解要好，那么更新这个最优解。重复上述过程，直到遗传代数达到预先设定的值。

程序运行过程会实时输出计算出的路线情况，最后会给出计算出的路线以及距离，并与最优解进行对比。

\begin{figure}[h]
	\subfigure[初始状态]{
		\includegraphics[width=0.25\textwidth]{0.png}
	}
	\subfigure[100代]{
		\includegraphics[width=0.25\textwidth]{100.png}
	}
	\subfigure[150代]{
		\includegraphics[width=0.25\textwidth]{150.png}
	}
	\subfigure[200代]{
		\includegraphics[width=0.25\textwidth]{200.png}
	}
	\caption{程序运行过程}
	\label{running}
\end{figure}

\section{结果分析}

\begin{figure}[h]
	\subfigure[ch130, 误差8.50\%]{
		\includegraphics[width=0.5\linewidth]{./garesult/ch130.png}
	}
	\subfigure[ch150, 误差7.47\%]{
		\includegraphics[width=0.5\linewidth]{./garesult/ch150.png}
	}
	\subfigure[eil101, 误差6,76\%]{
		\includegraphics[width=0.5\linewidth]{./garesult/eil101.png}
	}
	\subfigure[kroC100, 误差8.72\%]{
		\includegraphics[width=0.5\linewidth]{./garesult/kroC100.png}
	}
	\subfigure[att48, 误差12.62\%]{
		\includegraphics[width=0.5\linewidth]{./garesult/att48.png}
	}
	\subfigure[gr202, 比最优解结果好]{
		\includegraphics[width=0.5\linewidth]{./garesult/gr202.png}
	}
	\caption{遗传算法执行结果}
	\label{result}
\end{figure}

\subsection{遗传算法结果分析}
本次实验在windows系统下执行。图\ref{result}是遗传算法的执行结果，可以看到对于前四个数据算法都表现出了较优的执行结果，无论是在路线的交叉性上还是在与最优解的误差上都有较好的表现。对于第5个数据，误差则略大，第5个数据的特点是点较少，且两个城市之间的距离非常大，这就导致对于最优解的城市排列要求非常苛刻，任意两个城市的排列顺序变化都可能导致解变坏很多。

而对于第6个数据出现了非常奇怪的情况，即遗传算法的解比给定的最优解要好，且经过了多次执行和验证，目前认定是数据集的问题。此数据计算出的路径可见附录。

经过上述实验结果可以分析，算法的总体表现较好，但在遇到苛刻的数据集时表现稍差，原因分析可能有以下两点：

\begin{enumerate}
	\item 迭代次数偏少。实验中本人实验迭代次数最多设置到了5000次，但是由于时间原因没有尝试更高次数的迭代次数，因此是否更多的迭代次数能够获得最优解是未知的。
	\item 后代的多样性偏少。在程序运行的实时过程中可以看到，随着运行时间的推进，会出现几百代最优路径也不更新一次的情况，这就说明程序很有可能一直陷入局部最优，或者后代的染色体类似，找不到更加新的后代。
\end{enumerate}

因此后续工作可以尝试在时间允许的情况下提高迭代次数和变异概率，尝试是否能有更优的结果产生。

\subsection{算法对比}

所有测试数据的计算结果如下:\footnote{模拟退火算法的计算结果来自同一组的徐浩添同学}

\begin{table}[h]
	\caption{算法结果对比}
	\centering
	\begin{tabular}{|c|c|c|c|c|c|}
		\hline
		\multirow{2}*{测试数据} &\multirow{2}*{最优解} & \multicolumn{2}{|c|}{遗传算法} & \multicolumn{2}{|c|}{模拟退火算法} \\
		\cline{3-6}
		& & 结果 & 误差 & 结果 & 误差 \\
		\hline
		ch130 & 6110 & 6631.11550492963 & 8.50\% & 6538.7 & 7\% \\
		\hline
		eil101 &642.3095358	&685.7220164	&	6.76\%	&	678.25 & 5.60\% \\
		\hline
		ch150	&6532.280933&	7020.521858	&	7.47\%	&	7200.06	&	10.20\% \\
		\hline
		kroC100	&20750.7625&	22561.08306	&	8.72\%	&	21464.59	&	3.40\% \\
		\hline
		att48&	33523&	37752	&	12.62\%	&	33966.14	&	1.30\% \\
		\hline
	\end{tabular}
\end{table}

遗传算法的结果与模拟退火算法的结果对比基本不相上下，但由于遗传算法的特性，在运行时间上慢于模拟退火算法(这也与初始温度和降温速度有关)。

\newpage

\section{结论与感悟}

\subsection{遗传算法}
\par 本次项目采用遗传算法求解旅行商问题，总体上分为思想与实现两个部分。首先根据课上老师所讲的遗传算法的原理，设计遗传算法用于旅行商问题的具体方法，包括染色体的含义，复制、交叉、变异在城市排列顺序上的体现。然后基于伪代码程序的实现，在组员的建议下使用了python，因为python能提供良好的批量数据的处理功能，以及丝毫不逊色于matlab的可视化界面，难点只有python语法的学习过程，不过语法问题也是每接触一门新语言上的必经之路。
\par 每一个数据集所对应的程序参数不一定相同，因此针对不同的数据集也许需要调整参数，例如变异概率等，因为每个数据集的特点不同，例如城市数量，城市的距离，改变任意两个城市后距离的变化，也就是启发式算法并不是一个程序编好后就能应对所有的测试集。
\par 本次项目在编写过程中遇到的主要困难有：
\begin{enumerate}
	\item 算法速度过慢。后来通过请教同学，这是由于没有及时淘汰劣势后代，和变异概率设置的过高造成的，因此程序在编写的时候给每一次的父代都设置了上限，一旦轮盘赌选择到了上限则停止选择。同时在交叉产生子代的时候就开始在两个子代中选择适应度更优的子代保留，保证了解的质量。
	\item 算法解质量较差。这是因为对于启发式算法的误区，认为启发式算法也应在短时间达到良好的效果，后来经同组同学指正，可以设置一个很大的迭代次数，让程序运行半小时甚至一小时后再对比之前的结果，这一问题也被顺利解决。
	\item 其他问题，例如调试的困难，语法理解错误等。这些错误均通过加中间结果输出的方式得到了有效解决，而下一步可以研究python有没有更好的调试方法。
\end{enumerate}

\par 通过以上分析可以看出，要设计一个好的遗传算法，要做到以下几点：

\begin{enumerate}
	\item 好的编码方式。合适的城市编码方式能极大地影响解的质量和算法复杂度。
	\item 参数的调整。需要调整交叉位置、概率的参数，选择的策略，变异的方式、概率的参数。
	\item 算法的终止条件，例如达到最优解的多少误差以内，或者遗传超过多少带就可以终止算法
\end{enumerate}

\par 根据题目的要求，所有100以上城市的数据最终都收敛到了最优解误差的10\%以内，而对于少量较为苛刻的数据略微超出10\%。后续工作可以尝试在时间允许的情况下提高迭代次数和变异概率，尝试是否能有更优的结果产生，或者尝试将遗传算法的中间过程与其他算法相结合，写出更优的选择和交叉策略。

\subsection{单点搜索与多点搜索对比}

模拟退火是一个常见的单点搜索例子。单点搜索最常见的问题就是陷入局部最优解，而模拟退火虽然有概率能跳出局部最优解，但由于对整个搜索空间的状况了解较少，很大程度上能进入构成最优解的关键区域搜索的概率很小。这个原因使得模拟退火算法的运算效率不高。此外，模拟退火算法对参数（如初始温度）的依赖性较强，且进化速度慢。

遗传算法是一个常见的多点搜索例子，具有良好的全局搜索能力，通过生成大量的初始染色体，即种群，使得遗传算法对于整个搜索空间的状况了解远优于模拟退火算法，而不会陷入局部最优解的快速下降陷阱。同时因为是多点搜索，在条件允许的情况下，利用它的内在并行性，可以方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的问题。所以采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是遗传算法中较难解决的问题。

\renewcommand\refname{参考文献}
\begin{thebibliography}{1}
	
	\bibitem{Ben-Shimon2015RecSys}
	Quang Minh Ha, Yves Deville, Quang Dung Pham, Minh Hoàng Hà, A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Drone, 2018.12
	\bibitem{Esra}
	 Esra'a Alkafaween, Ahmad B. A. Hassanat, Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness, 2018.1
	\bibitem{ff}
	 Esra'a O Alkafaween, Novel Methods for Enhancing the Performance of Genetic Algorithms, 2018.1
	\bibitem{gg}
	Yihui He, Ming Xiang, An Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem, 2017.5
	\bibitem{hh}
	Hassan Ismkhan, Kamran Zamanifar, Study of Some Recent Crossovers Effects on Speed and Accuracy of Genetic Algorithm, Using Symmetric Travelling Salesman Problem, 2015.4
	
	
	
	
	
	
	
	
	
	
\end{thebibliography}






















